#ifndef FSTX_ALLPATHS_H__
#define FSTX_ALLPATHS_H__

namespace fst {
template<class Arc, class C>
int AllPaths(const Fst<Arc>& fst, C& c) {
	typedef typename Arc::StateId S;
	typedef typename Arc::Weight W;
	typedef typename Arc::Label L;
	typedef ArcIterator< Fst<Arc> > AI;

  struct Element {
    L label;
    W cost;
  };

	vector<AI*> arc_iterators;
	list<L> current_path;
  list<W> current_cost;
  current_cost.push_back(W::One());
	int num_paths = 0;

  S start = fst.Start();
  if (start == kNoStateId) {
    return -1;
  }
  LifoQueue<S> queue;
  queue.Enqueue(start);

  while(!queue.Empty()) {
    S s = queue.Head();
    queue.Dequeue();
    if ( s >= arc_iterators.size()) 		
      arc_iterators.resize(s + 1);

		if (arc_iterators[s] == NULL) {
			arc_iterators[s] = new AI(fst, s);
			if (fst.Final(s) != W::Zero())
				c(current_path, current_cost.back());
		}

    AI& iter = *arc_iterators[s];		    
    if (!iter.Done()) {      
      queue.Enqueue(s);
      const Arc& arc = iter.Value();
      iter.Next();				
      current_path.push_back(arc.ilabel);
      current_cost.push_back(Times(arc.weight, current_cost.back()));
      queue.Enqueue(arc.nextstate);			
    } else {
      if (current_path.size()) {
        current_path.pop_back();
        current_cost.pop_back();
      }
      if (s != fst.Start()) {
        delete arc_iterators[s];
        arc_iterators[s] = NULL;
      }
    }		    
  }
  for (size_t i = 0; i != arc_iterators.size(); ++i)
    delete  arc_iterators[i];
  return num_paths;
}


template <class Label, class Weight>
struct PathInserter {
  PathInserter(const SymbolTable* syms, vector<string>* strings) 
    : syms_(syms), strings_(strings) { }

  void operator()(const list<Label>& path, const Weight& w) {
    stringstream ss;
    typename list<Label>::const_iterator it = path.begin();
    for ( ; it != path.end(); ++it) {
      const Label& l = *it;
      if (syms_ == 0)
        ss << l << " ";
      else
        ss << syms_->Find(l);
    }
    ss << " (" << w << ")";
    string str = ss.str();
    strings_->push_back(str);
  }

  const SymbolTable* syms_;
  vector<string>* strings_;
};

template<class Arc>
void AllPaths(const Fst<Arc>& fst, const SymbolTable* syms,
  vector<string>* strings) {
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  PathInserter<Label, Weight> pi(syms, strings);
  AllPaths(fst, pi);
}
}
#endif //#define FSTX_ALLPATHS_H__